#include <stdio.h>

#define MAX 5

/* Program description:
   Depth first search for a graph

   Algorithm design
   Using adjacency matrix to store the graph
   Using stack to store the nodes being visited
   From the stack,
     pop the node
     if the neighbor of the nodes have not been visited, push the neighbor
   until stack is empty (or the nodes have all been visited)
*/

int dfs(int adj[][MAX],int visited[],int start)
{
    int stack[MAX];
    int top=-1,i;
    
    printf("%d ",start);
    visited[start]=1;
    stack[++top]=start;
    while(top!=-1)
    {
        start=stack[top];
        for(i=0;i<MAX;i++)
        {
            if(adj[start][i]&&visited[i]==0)
            {
                stack[++top]=i;
                printf("%d ",i);
                visited[i]=1;
                break;
            }
        }

        if(i==MAX)
            top--;
    }

    return 0;
}

int main()
{
    int adj[MAX][MAX]={{0,0,1,1,0},{0,0,0,0,0},{0,1,0,0,1},{0,0,0,0,1},{0,0,0,1,0}};
    int visited[MAX]={0};

    printf("DFS Traversal : ");
    dfs(adj,visited,0);
	printf("\n");
    
    return getchar();
}